import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-10-30
 * Time: 18:55
 */
public class demo {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];

        //把p的字符频次扔进哈希表hash2中
        for (int i = 0; i < p.length(); i++) {
            char ch = p.charAt(i);
            hash2[ch - 'a']++;
        }
        //滑动窗口
        int left = 0, right = 0;
        while (right < s.length()) {
            //进窗口
            char in = s.charAt(right);
            hash1[in - 'a']++;
            //判断
            if (right - left + 1 > p.length()) {
                //出窗口
                char out = s.charAt(left);
                hash1[out - 'a']--;
                left++;
            }
            //更新结果
            //比较两个哈希表
            boolean flg = true;
            for (int i = 0; i < 26; i++) {
                if (hash1[i] != hash2[i]) {
                    //不是
                    flg = false;
                }
            }
            if (flg) {
                ret.add(left);
            }
            right++;
        }
        return ret;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        //1. 把words扔进哈希表中
        HashMap<String, Integer> hash = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            hash.put(words[i], hash.getOrDefault(words[i], 0) + 1);
        }

        int len = words[0].length();

        //执行len次滑动窗口
        for (int i = 0; i < len; i++) {
            int left = i, right = i;
            int count = 0;//有效字符串的个数
            HashMap<String, Integer> hashMap = new HashMap<>();
            //滑动窗口
            while (right < s.length() && right + len <= s.length()) {
                //进窗口+维护count
                String in = s.substring(right, right + len);
                hashMap.put(in, hashMap.getOrDefault(in, 0) + 1);
                if (hashMap.get(in) <= hash.getOrDefault(in, 0)) {
                    count++;
                }

                //判断

                while ((right - left + 1) > len * words.length) {
                    //需要出窗口+维护count
                    String out = s.substring(left, left + len);
                    if (hashMap.get(out) <= hash.getOrDefault(out, 0)) {
                        count--;
                    }
                    hashMap.put(out, hashMap.get(out) - 1);
                    left += len;
                }
                if (count == words.length) {
                    ret.add(left);
                }
                right += len;
            }
        }
        return ret;
    }

    public String minWindow(String ss, String tt) {
        // 数组模拟哈希表
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];// 保存t的频次

        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int count = 0;// t字符串中字符种类个数
        // 先把t的频次保存
        for (char ch : t) {
            if (hash2[ch] == 0) {
                count++;
            }
            hash2[ch]++;
        }

        // 滑动窗口启动
        int left = 0, right = 0, kinds = 0;
        int minLen = Integer.MAX_VALUE, begin = -1;
        while (right < s.length) {
            // 进窗口+维护kinds
            char in = s[right];
            hash1[in]++;
            // 维护有效字符种类
            if (hash1[in] == hash2[in]) {
                kinds++;
            }

            // 判断,如果kinds==count,也就是说hash1有效字符种类和hash2一样
            while (kinds == count) {
                // 更新结果,起始位置和最短长度
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    begin = left;
                }

                // 出窗口+维护kinds
                char out = s[left];
                // 出之前判断有效字符种类
                if (hash1[out] == hash2[out]) {
                    kinds--;
                }
                //出窗口
                hash1[out]--;
                left++;
            }
            right++;
        }
        if (begin == -1) {
            return new String();
        }
        return ss.substring(begin, begin + minLen);
    }
}